package com.yaoli.ajob;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by will on 2017/7/9.
 */
public class _637_AverageofLevelsinBinaryTree {
    public List<Double> averageOfLevels(TreeNode root) {

        List<Double> res = new ArrayList<Double>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            int len = queue.size();

            Double total = 0.0;

            while(size != 0){
                TreeNode temp = queue.poll();

                total = total + temp.val;

                if(temp.left != null){
                    queue.offer(temp.left);
                }

                if(temp.right != null){
                    queue.offer(temp.right);
                }

                size--;
            }

            res.add(total/len);
        }

        return res;
    }
}
